/*
 * Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
 */
#include <string>
using namespace std;

class Solution {
public:
    /* O(n^2) */
    string longestPalindrome(string s) {
        int len = s.length();
        int curr_length = 0;
        if (len <= 1) {
            return s;
        }
        string smax;
        for (int i = 0; i < len; i++) {
            curr_length = 0;
            for (int j = 1; i-j >= 0 && i+j < len; j++) {
                if (s[i-j] != s[i+j]) {
                    break;
                }
                curr_length++;
            }
            if (smax.length() < curr_length*2+1) {
                //smax = s.substr(i-curr_length, curr_length*2+1);
                smax = string(s.begin()+i-curr_length, s.begin()+i+curr_length+1);
            }
            curr_length = 0;
            for (int j = 0; i-j >= 0 && i+j+1 < len; j++) {
                if (s[i-j] != s[i+j+1]) {
                    break;
                }
                curr_length++;
            }
            if (smax.length() < curr_length*2) {
                //smax = s.substr(i-curr_length+1, curr_length*2);
                smax = string(s.begin()+i-curr_length+1, s.begin()+i+curr_length+1);
            }
        }
        return smax;
    }
};

int main() {
    return 0;
}
